<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        /* 
        多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。
多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。
现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。
        */
       /* 
       5 2
1 2 3 4 5
out 6
长度为1: [2], [4]
长度为2: 无
长度为3: [1,2,3], [3,4,5]
长度为4: [1,2,3,4], [2,3,4,5]
长度为5: 无
共6个区间的和谐值之和可以被2整除。
       */
      function Solution(tree_num,ai,tree){
          let mod = new Array(ai).fill(0)
          // 处理子数组本身就能整除的问题，因为有余数第一次遇到不需要加，整除第一次需要加
          mod[0] = 1
          // 同余定理 sum(i)%m == sum(i+n)%m
          // i+1 -》 i+n 是一个可以整除m的子数组
          let ans = 0
          let sum = 0
          for(let i = 0; i < tree_num; i++){
              sum += tree[i]
              let index = sum % ai
              ans += mod[index]
              mod[index]++
          }
          return ans
      }
      console.log(Solution(5,2,[1,2,3,4,5]))
    </script>
</body>
</html>